﻿// 4595. 网格着色.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

/*
https://www.acwing.com/problem/content/4598/



某人为某场比赛出了这样一道题：

有一个 M
 行 N
 列的网格矩阵。

矩阵的行从上往下依次编号为 1∼M
，矩阵的列从左往右依次编号为 1∼N
。

第 x
 行第 y
 列的方格可以描述为 (x,y)
。

矩阵中有 B
 个方格是阻塞方格，它们的具体位置已知。

现在，有 K
 种不同的颜色，用于给网格矩阵着色，具体着色规则为：

每个未阻塞的方格都必须被着色。
每个阻塞的方格都不能被着色。
每个被着色方格的颜色都必须是给定的 K
 种颜色之一。
没有两个垂直相邻的方格具有相同的颜色，即方格 (x,y)
 和方格 (x+1,y)
 不能包含相同的颜色。
请问共有多少种不同的着色方案，请输出对 100,000,007
 取模后的结果。

以上就是此人所出题目的完整描述。

在出完后，他十分激动的将题目和数据交给了赛事举办方。

不幸的是，比赛前夕，赛事举办方却发现他给的数据存在问题。

他给的数据中缺少了 M
 的值，幸运的是，其他输入数据以及输出结果都是正确且存在的。

现在，请你帮忙计算 M
 的最小可能值。

输入格式
第一行包含整数 T
，表示共有 T
 组测试数据。

每组数据第一行包含四个整数 N,K,B,R
，其中 R
 为方案总数取模后的结果。

接下来 B
 行，每行包含两个整数 x,y
，表示其中一个阻塞方格的位置为 (x,y)
。

阻塞方格位置两两不同。

输出格式
每组数据输出一行结果，格式为 Case i: x，其中 i
 为组别编号（从 1
 开始），x
 为 M
 的最小可能值。

数据范围
1≤T≤150
,
1≤M,N≤108
,
2≤K≤108
,
0≤B≤500
,
0≤R<108+7
,
1≤x≤M
,
1≤y≤N
。

输入样例：
4
3 3 0 1728
4 4 2 186624
3 1
3 3
2 5 2 20
1 2
2 2
2 3 0 989323
输出样例：
Case 1: 3
Case 2: 3
Case 3: 2
Case 4: 20
*/

int main()
{
    std::cout << "Hello World!\n";
}

 